The evolution of computer technology has resulted in the creation of a sophisticated technical area devoted to the representation of graphical information generated by computers. This area is termed computer graphics. One technique that is commonly used in computer graphics is that of producing a set of points and connecting these points with straight lines. The resulting combination of points and straight lines are displayed on the computer graphics terminal display which normally consists of a cathode ray tube. It is also desirous to produce curves relative to certain points on the display. Generating smooth curves on a graphical display is often done by constructing a composite curve that is accomplished by fitting successive low-degree polynomials to successive groups of data points. The resulting piecewise polynomial function will appear to be a continuous curve but will in general have perceptible discontinuities in slopes of curvative at joints between successive curve segments unless specific curve types or forms are used. This technique is a kin to the use of a "French curve" in drafting where it is desired to fit a curve for a complete set of points by using segments of the French curve surface. Using the French curve, a draftsman will attempt to fit a small number of points onto a segment of the French curve edge and draw a portion of this segment. The draftsman will then continually connect additional segments together by repeating this technique until all the points have been included in a curve. In computer graphics, this same end is accomplished by fitting the points with the successive low-degree polynomial equations to produce the curve values in the dimensional coordinate system.
In a two-dimensional space, a curve is often expressed as a function of the orthogonal components x and y, i.e., Y is equal to f(x). In a three-dimensional coordinate system, the x, y and z coordinates may also be represented as functions of one or two of the orthogonal components. However, these representations may cause difficulty in generating the coordinate values. One alternative technique is to use a parametric representation of the curve or a representation where each coordinate value on a curve is represented as a function of some common variable, that is, a variable common to all coordinate components. For a three dimensional system, such a variable may be described as t resulting in the following: x=f(t); y=g(t); and c=h(t); for 0&lt;t&lt;1. A further representation is a parametric cubic curve that is represented by third order polynomials. EQU x=f(t)=a.sub.x t.sup.3 +b.sub.x t.sup.2 +c.sub.x t+d.sub.x EQU y=g(t)=a.sub.y t.sup.3 +b.sub.y t.sup.2 +c.sub.y t+d.sub.y EQU z=h(t)=a.sub.z t.sup.3 +b.sub.z t.sup.2 +c.sub.z t+d.sub.z
Cubic curves are important because no lower-order representation of curve segments can provide either continuity of position and slope or continuity of slope and curvature at the point where the curve segments meet. Cubic curves are also the lowest order curves that can render non-planar curves in three dimensions.
The equation for the x coordinate above may be represented in the following matrix fashion: ##EQU1##
The coefficient vector [c.sub.x ] can be derived to yield curves of many different properties. The most useful derivations are the Hermite form, the Bezier form and the B-Spline form. One can break the coefficient vector into the cross product of a 4.times.4 basis matrix [M] multiplied by a columnar geometry vector [G.sub.x ].
A general review of the forms of these curves is contained in the publication entitled Fundamentals of Interactive Computer Graphics by James D. Foley and Andries VanDam published by Addison-Wesley Publishing Company (1982); Principles of Interactive Computer Graphics, second edition, by William M. Newman and Robert F. Sproull published by McGraw-Hill Book Company (1979); and Computer Aided Geometric Design, edited by Robert E. Barnhill and Richard F. Riesenfeld from Academic Press (1974).
The one embodiment of the following invention is a method and apparatus for producing curves from the B-Spline form. The B-Spline form is explained Fundamentals of Interactive Computer Graphics, page 521 through 523 (herein incorporated by reference).
One technique in generating graphics with splines is disclosed in the IBM Technical Disclosure Bulletin, Volume 25, No. 11b (April, 1983) entitled "High Speeds for Generating or Updating Graphics with Splines on a Screen". The technique disclosed illustrates an analog computer implementation using an exact integration to evaluate the polynomial.
Using digital processors, floating point arithmetic is required to compute the matrix arithmetic operations for computing the coordinate values. This floating point arithmetic requirement is disadvantageous because (1) it is very time consuming and (2) it is not entirely accurate. The inaccuracy results from the requirement of repetitive floating point operations. By its very nature, a single floating point operation is inexact resulting in a small error. This small error is compounded each time the results from one floating point operation is used in a second floating point operation. Therefore, performing a series of floating point operations will result in a compounded inaccuracy by its very nature.
It is an object of the present invention to provide a method and apparatus for providing curves using the B-Spline form in a more accurate manner than provided by the traditional floating point technique.
It is also an object of the present invention to provide a high-speed method and apparatus for producing B-Spline curves.